#include"BinaryTree.h"

BTNode* BinaryTreeCreate(BTDataType* a,int* pi)
{
	assert(a);
	assert(pi);

	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));

	root->_data = a[(*pi)++];
	
	root->_left = BinaryTreeCreate(a,  pi);
	root->_right = BinaryTreeCreate(a,  pi);
	return root;
	
}
void BinaryTreeDestory(BTNode** root)
{
	assert(root);
	if (!*root)
	{
		return;
	}
	BinaryTreeDestory(&(*root)->_left);
	BinaryTreeDestory(&(*root)->_right);
	free(*root);
	*root = NULL;


}

int BinaryTreeSize(BTNode* root)
{
	
	if (root == NULL)
	{
		return 0;
	}

	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->_left == NULL && root->_right == NULL)
		return 1;

	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right)  ;
}
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	
	if (k == 1)
	{
		return 1;
	}
	return 
	BinaryTreeLevelKSize(root->_left, k - 1)+
	BinaryTreeLevelKSize(root->_right, k - 1);

}
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (!root)
	{
		return NULL;
	}
	if (root->_data == x)
		return root;
	BTNode*left = BinaryTreeFind(root->_left, x);
	if (left)
		return left;
	BTNode* right = BinaryTreeFind(root->_right, x);
	if (right)
		return right;
	return NULL;
}

void BinaryTreePrevOrder(BTNode* root)
{
	if (!root)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);

}
void BinaryTreeInOrder(BTNode* root)
{
	if (!root)
	{
		printf("NULL ");
		return;
	}
	
	BinaryTreeInOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreeInOrder(root->_right);
}
void BinaryTreePostOrder(BTNode* root)
{
	if (!root)
	{
		printf("NULL ");
		return;
	}

	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%c ", root->_data);

}

void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if(root)
	QueuePush(&q,root);
	while (!is_empty(&q))
	{
		BTNode* front = QueueTop(&q);
		printf("%c ", front->_data);
		QueuePop(&q);
		if(front->_left!=NULL)
		QueuePush(&q, front->_left);
		if (front->_right != NULL)
		QueuePush(&q, front->_right);

	}

}
bool BinaryTreeComplete(BTNode* root)
{

	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!is_empty(&q))
	{
		BTNode* front = QueueTop(&q);
		if (!front)
		{
			while(!is_empty(&q))
			{
				BTNode* front = QueueTop(&q);
				if (front)
					return false;
				QueuePop(&q);
			}
			return true;
		}
		printf("%c ", front->_data);
		QueuePop(&q);
		QueuePush(&q, front->_left);
		QueuePush(&q, front->_right);

	}
}